#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct RES {
    int maxsum;
    int i, j;
} RES;

int MaxSubSequenceSum1(const int A[], int N) {
    int res = 0;
    for (int i = 0; i < N; i++)
        for (int j = i; j < N; j++) {
            int tempSum = 0;
            for (int k = i; k <= j; k++)
                tempSum += A[k];
            if (tempSum > res)
                res = tempSum;
        }
    return res;
}

int MaxSubSequenceSum2(const int A[], int N) {
    int res = 0;
    for (int i = 0; i < N; i++) {
        int tempSum = 0;
        for (int j = i; j < N; j++) {
            tempSum += A[j];
            if (tempSum > res)
                res = tempSum;
        }
    }
    return res;
}

static int MaxSub(const int A[], int begin, int end) {
    //基准情况：当begin==end时，返回0和该数之间的最大值
    if (begin == end)
        return A[begin] > 0 ? A[begin] : 0;

    //一般逻辑
    int leftMax = 0, rightMax = 0, middleMax = 0;
    leftMax = MaxSub(A, begin, (begin + end) / 2);
    rightMax = MaxSub(A, (begin + end) / 2 + 1, end);

    int leftSum = 0, leftTemp = 0, rightSum = 0, rightTemp = 0;
    for (int i = (begin + end) / 2; i >= begin; i--) {
        leftTemp += A[i];
        if (leftTemp > leftSum)
            leftSum = leftTemp;
    }
    for (int i = (begin + end) / 2 + 1; i <= end; i++) {
        rightTemp += A[i];
        if (rightTemp > rightSum)
            rightSum = rightTemp;
    }
    middleMax = leftSum + rightSum;

    //求三者最大值即可
    int res = leftMax;
    res = res >= middleMax ? res : middleMax;
    res = res >= rightMax ? res : rightMax;

    return res;
}

int MaxSubSequenceSum3_1(const int A[], int N) {
    return MaxSub(A, 0, N - 1);
}

int MaxSubSequenceSum3(const int A[], int N) {
    //基准情况--------------------------------------------------------
    if (N == 1)
        return A[0] > 0 ? A[0] : 0;

    int leftMax = 0, rightMax = 0, crossMax = 0;
    int res = 0;

    //不断推进--------------------------------------------------------
    //求leftMax
    leftMax = MaxSubSequenceSum3(A, N / 2);

    //求rightMax
    int partA[N - N / 2];

    int index = 0;
    for (int i = N / 2; i < N; i++) {
        partA[index] = A[i];
        index++;
    }
    rightMax = MaxSubSequenceSum3(partA, N - N / 2);

    //求crossMax
    int temp = 0, leftSum = 0;
    for (int i = N / 2 - 1; i > -1; i--) {
        temp += A[i];
        if (temp > leftSum)
            leftSum = temp;
    }
    int rightSum = 0;
    temp = 0;
    for (int i = N / 2; i < N; i++) {
        temp += A[i];
        if (temp > rightSum)
            rightSum = temp;
    }
    crossMax = rightSum + leftSum;

    //求最大值并返回
    res = leftMax;
    if (rightMax > res)
        res = rightMax;
    if (crossMax > res)
        res = crossMax;

    return res;
}

// res为结果结构体，保存最大子序列的和、子序列的起始位置
int MaxSubSequenceSum4(const int A[], int N, RES* res) {
    int maxSum = 0, thisSum = 0;
    res->i = 0;
    res->j = 0;
    int flag1 = 0;
    for (int i = 0; i < N; i++) {
        thisSum += A[i];
        if (thisSum > maxSum) {
            res->i = flag1;
            res->j = i;
            maxSum = thisSum;
        }
        if (thisSum < 0) {
            if (i < N - 1)
                flag1 = i + 1;
            thisSum = 0;
        }
    }
    res->maxsum = maxSum;
    return maxSum;
}

const int N = 1000;

int main() {
    int array[N];
    for (int i = 0; i < N; i++) {
        srand(i);
        array[i] = rand() % 200 - 100;
        printf("%d\t", array[i]);
    }

    clock_t start, stop;

    start = clock();
    printf("\n\n%d\n", MaxSubSequenceSum1(array, N));
    stop = clock();
    printf("The duration01 is: %lf\n", (double)(stop - start) / CLOCKS_PER_SEC);

    start = clock();
    printf("\n\n%d\n", MaxSubSequenceSum2(array, N));
    stop = clock();
    printf("The duration02 is: %lf\n", (double)(stop - start) / CLOCKS_PER_SEC);

    start = clock();
    printf("\n\n%d\n", MaxSubSequenceSum3_1(array, N));
    stop = clock();
    printf("The duration03 is: %lf\n", (double)(stop - start) / CLOCKS_PER_SEC);

    start = clock();
    RES res1;
    printf("\n\n%d\n", MaxSubSequenceSum4(array, N, &res1));
    printf("The beginning is %d\nThe ending is %d\n", res1.i, res1.j);
    stop = clock();
    printf("The duration04 is: %lf\n", (double)(stop - start) / CLOCKS_PER_SEC);

    return 0;
}